#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "queue"

using namespace std;

/*HJJ QQ479287006
 *116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。
 输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

class Node {
public:
    int val;
    Node *left;
    Node *right;
    Node *next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node *_left, Node *_right, Node *_next)
            : val(_val), left(_left), right(_right), next(_next) {}
};


//返回头结点啊 TODO
//总感觉这个看了一眼 就一眼别人题解。然后自己迅速写出来了 。。自己原来想的是层次便利递归 那个求个高度啥的（应该是不行）
Node *connect(Node *root) {

    if (!root)
        return root;

    //先序便利
    if (root->left)
        root->left->next = root->right;

    if (root->right && root->next)
        root->right->next = root->next->left;

    connect(root->left);
    connect(root->right);
    return root;//其实这个root 就是头不用想太多 因为你开头就是头节点 递归调用也没经过root=root->next 这种肯定是返回头了

}

//层次便利 我擦确实一边过了
Node *connectT(Node *root) {

    queue<Node *> q;
    q.push(root);

    int front = 0;
    int rear = 1;
    int last = 1;
    while (!q.empty()) {
        Node *temp = q.front();
        q.pop();
        front++;

        if (temp->left) {
            q.push(temp->left);
            rear++;
        }

        if (temp->right) {
            rear++;
            q.push(temp->right);
        }


        if (last == front) {
            // last=rear;
            while (last != rear) {
                Node *n1 = q.front();
                q.pop();
                Node *n2 = q.front();
                q.pop();
                n1->next = n2;
                last++;
            }

        }

    }


}